3D CAD/CAM/CAE (CAx) models are widely used by product development organizations. Most product development organizations have large databases or repositories of 3D models. These repositories necessarily archive the 3D shape or geometry of the 3D models. The repositories also usually archive related textual and multi-media data associated with the models.
Repositories for 3D models in a product development organization can rapidly grow in size over time as more and more 3D models get archived into the system. Larger repositories of 3D models necessarily require larger amounts of time and result in larger costs for maintenance. It is therefore important to keep the size of these repositories to the minimum required in order to save maintenance costs. Furthermore, an automated system for managing the repositories is necessary to save on maintenance time.
Traditionally, most product development organizations usually develop proprietary conventions for assigning unique names and subjective attributes to archived 3D models. These conventions are dictated by the needs of a particular business model and are based on a multitude of industry standard, software and vendor specific keywords. These names and attributes are stored in the repositories along with the 3D shape or geometry information. However, due to their inherent subjective nature these conventions are difficult to enforce across a large number of engineers and designers, and across different departments in the same organization.
Reuse of existing 3D shape and related data when developing a new product significantly decreases the time to market and cost for the product. Reuse is effective during all stages of the design-to-manufacturing cycle. Furthermore, where direct reuse of existing model is permitted, it also saves on maintenance costs related to storing duplicate models in a repository. However, browsing for and locating a reusable model in a large repository can be a tedious exercise, the cost of which sometimes exceeds the cost savings related to reuse. This is due to the fact that current CAx/PDM repositories only allow searching based on the model names and subjective attributes, and are thus lacking in robustness.
It is of interest to engineers and designers to have a method to quickly identify reusable models based directly on their 3D shape or geometry. This is because the 3D shape similarity between models is often an indication of design, analysis and manufacturing process similarity. A 3D shape based method can be used as a tool in conjunction with existing search systems available in CAx/PDM repositories, to quickly identify reusable models.
Prior art systems are available for 3D shape based searching. The key parameters for evaluating such shape based search methods are: (i) The ability to discriminate a model sufficiently among a large set of dissimilar models; (ii) Tolerance to relatively small changes that occur across similar models; (iii) Computationally inexpensive to derive and compare against many models. Much of the prior art has been concentrated on general and approximate methods, with less emphasis on application specific and accurate methods. Moreover, most prior art techniques do not meet the three said evaluation criteria. The prior art methods used can be broadly grouped into four categories—gross parameters, statistical measures, graph based methods and transform based methods.
Briefly considering the four generic categories, gross shape measures capture gross properties of the 3D model such as volume, surface area, moments, etc. Gross measures may also include certain domain specific information (like molecular weight, in 3D molecular databases). Several gross parameters (“crinkliness”, “compactness” etc.) have been used in describing the shape and matching in the domain of CAD databases. (See Rea, J., Corney, J. R., Clark, D. E. R., Pritchard, J., Breaks, M. L., and MacLeod, R. A.: Part-Sourcing in a Global Market. Proceedings of ICeCE 2001. 2001 International Conference on eCommerce Engineering: New Challenges for Global Manufacturing in the 21st Century, Sep. 16-18, 2001. Xi'an, P. R. China.) The use of “feature vectors” and moments as gross parameters for 3D shape comparison have also been described. (See Vranic, D. V., and Saupe, D.: 3D Model Retrieval. In: Proceedings of the Spring Conference on Computer Graphics and its Applications (SCCG2000) (ed. Falcidieno, B.), Budmerice, Slovakia, May 2000, pp. 89-93.)
Gross parameters describe only a subset of the information comprising shape and related properties of 3D models. Therefore gross measures can be used effectively only in small sized databases where domain specific information can be leveraged. Gross parameters usually become too indiscriminating for repositories containing a large number of models.
Statistical shape measures capture the shape of a model by some form of sampling. Statistical shape histograms have been used for nearest neighbor search and classification in 3D molecular databases. (See Ankerst, M., Kastenmüller, G., Kriegel, H.-P., and Seidl, T.: 3D Shape Histograms for Similarity Search and Classification in Spatial Databases. In Proc. 6th International Symposium on Spatial Databases (SSD'99), Hong, Kong, China, July 1999.) Further, various forms of shape distributions for comparing 3D models, have also been analyzed. (See Osada, R., Funkhouser, T., Chazelle, B., and Dobkin, D.: Matching 3d models with shape distributions. International Conference on Shape Modeling and Applications. ACM SIGGRAPH, The Computer Graphics Society and EUROGRAPHICS, IEEE Computer Society Press, Genova, Italy, May 7-11 2001, pp. 154-166.) Another statistical 3D shape similarity measure has been described which is based on sampling of gross measures like moments, average surface distance and its variance along the principal axes of inertia; (See Ohbuchi, R., Otagiri, T., Ibato, M., and Takei, T.: Shape-Similarity Search of Three-Dimensional Models Using Parameterized Statistics. In the proceedings of the Pacific Graphics 2002, Beijing, China, October 2002, pp. 265-274.)
Statistical shape based methods are based on sampling a large number of sample measures, and are hence relatively expensive to compute in comparison to gross parameters. However, the major drawback of such statistical measures (as in the case of gross parameters) is that their discriminating power decreases rapidly with increase in the number of models in the repository. Moreover, as the complexity of the 3D model increases most statistical distributions tend towards some standard shaped distributions (like the normal distribution).
Graphs describe shape using some connectivity structure. Graph based methods have been used in case of 2D shape matching, in fields like character recognition and silhouette matching. In 3D, a method of matching 3D models has been developed using connected skeletal approximations called multi-resolution ‘Reeb Graphs’. (See Hilaga, M., Shinagawa, Y., Kohmura, T., and Kunii, Tosiyasu L.: Topology matching for fully automatic similarity estimation of 3D shapes. In SIGGRAPH, ACM, ACM Press, New York, N.Y., USA, August 2001, pp. 203-212.) Further, various feature-graph based techniques have been developed using manufacturing features of CAD models and graph based heuristics for determining the similarity between different 3D CAD models. (See Elinson, A., Nau, D. S., and Regli, W. C.: Feature-based similarity assessment of solid models. In: Christoph Hoffman and Wim Bronsvoort (ed.): Fourth Symposium on Solid Modeling and Applications, pp. 297-310, New York, N.Y., USA, May 14-16 1997. ACM, ACM Press, Atlanta, Ga.)
Graph based methods in 3D (as against in 2D) involve steps which are computationally very expensive such as computing the 3D skeleton graph or extracting features for forming feature nodes in the feature graph. Moreover, adapting the graph based techniques for handling models with multiple bodies (with or without connectivity) and surface models is a non-trivial problem.
Transform based methods usually transform the 3D shape into alternative representations of reduced dimension in terms of certain key coefficients. This makes the 3D shape matching task much simpler (as in the case of gross parameters and statistical measures) and simultaneously minimizes the loss of shape information. Transform based methods are also relatively inexpensive to compute as compared to graph based methods.
Transforms based methods are usually applied on some approximation of the 3D model, like the voxel approximation. A voxellized representation allows various relatively fast and discrete mathematical transforms to be applied to the 3D model, which retain only the most important and relevant characteristics of shape information. The “Reflective Symmetry” transform and the “Spherical Harmonics” transform have been used directly on the voxellized representation of the 3D model. (See Kazhdan, M., Chazelle, B., Dobkin, D., Funkhouser, T. and Rusinkiewicz, S.: A reflective symmetry descriptor for 3D models. Algorithmica, Special Issue on Shape algorithmics. 2003, and Funkhouser, T., Min, P., Kazhdan M., Chen, J., Halderman, A., Dobkin, D., and Jacobs D.: A Search Engine for 3D Models. ACM Transactions on Graphics, 22(1), pp. 83-105, January 2003.) Further, the use of the “3D Discrete Fourier” transform on a voxellized representation of the 3D model has been proposed. (See Vranic, D. V., and Saupe, D.: 3D Shape Descriptor Based on 3D Fourier Transform. In: Proceedings of the EURASIP Conference on Digital Signal Processing for Multimedia Communications and Services (ECMCS 2001) (editor Fazekas, K.), Budapest, Hungary, September 2001, pp. 271-274.) The “3D Hough” transform has also been used as a 3D shape descriptor. (See Zaharia, T., and F. Preteux, F.: Shape-based retrieval of 3D mesh models. In Proc. 2002 IEEE International Conference on Multimedia and Expo (ICME'2002), Lausanne, Switzerland, August 2002.)
In most transform based techniques (as against other methods) it is necessary to make the 3D model invariant to affine transforms. Therefore, several of the transform based methods tend to neglect the phase information associated with the transform in order to achieve affine invariance. In contrast, some transform based methods perform a prior pose-estimation step to orient the 3D model into a canonical pose before applying the transforms.
In summary, while gross and statistical measures are invariant to affine transformations, these measures are usually too indiscriminating for large repositories of models. Graph based methods can be used to capture structural, topology or feature information in a model, but these methods are computationally very expensive for non-trivial models. In contrast, the availability of a large number of existing transform based techniques allows for encoding various forms of shape data efficiently.